package Q386

import java.util.ArrayList


class Test {

}

//字典序排数
//给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
class Solution2 {
    fun lexicalOrder(n: Int): List<Int> {
        var res = ArrayList<Int>()
        for (i in 1..9) {
            dfs(n, i, res)
        }
        return res
    }

    private fun dfs(n: Int, target: Int, res: MutableList<Int>) {
        var target = target
        if (target > n) {
            return
        }
        res.add(target)
        target *= 10
        for (i in 0..9) {
            dfs(n, target + i, res)
        }
    }

}

class Solution {
    fun lexicalOrder(n: Int): List<Int> {
        val res = ArrayList<Int>()
        for (i in 1..9) dfs(n, i, res)
        return res
    }


    private fun dfs(n: Int, target: Int, list: MutableList<Int>) {
        var target = target
        if (target > n) return
        list.add(target)
        target *= 10
        for (i in 0..9) dfs(n, target + i, list)
    }

}